// https://leetcode.cn/problems/unique-paths-iii/description/

// 算法思路总结：
// 1. 深度优先搜索统计所有唯一路径数量
// 2. 从起点到终点，必须经过所有无障碍格子恰好一次
// 3. 使用path计数已访问的无障碍格子数
// 4. 到达终点时检查是否访问了所有无障碍格子
// 5. 回溯时恢复path和vis状态
// 6. 时间复杂度：O(4ᵏ)（k为无障碍格子数），空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    int m, n;
    int ZeroNums;
    int path, ret;
    int sx, sy;
    int ex, ey;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    bool vis[21][21];

    int uniquePathsIII(vector<vector<int>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        ZeroNums = 0, path = 0, ret = 0;
        memset(vis, 0, sizeof(vis));

        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if (grid[i][j] == 1)
                {
                    sx = i, sy = j;
                }
                else if (grid[i][j] == 2)
                {
                    ex = i, ey = j;
                }
                else if (grid[i][j] == 0)
                {
                    ZeroNums++;
                }
            }
        }

        vis[sx][sy] = true;
        dfs(grid, sx, sy);

        return ret;
    }

    void dfs(vector<vector<int>>& grid, int a, int b)
    {
        if (a == ex && b == ey)
        {
            if (path == ZeroNums)
            {
                ret++;
            }
            return ;
        }

        for (int i = 0 ; i < 4 ; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 0 && y >= 0 && x < m && y < n && vis[x][y] == false && grid[x][y] != -1)
            {
                if (grid[x][y] == 0)
                {
                    path++;
                }
                vis[x][y] = true;

                dfs(grid, x, y);
                
                vis[x][y] = false;
                if (grid[x][y] == 0)
                {
                    path--;
                }
            }
        }
    }
};

int main()
{
    vector<vector<int>> grid1 = {
        {1, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 2, -1}
    };

    vector<vector<int>> grid2 = {
        {1, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 2}
    };

    Solution sol;

    cout << sol.uniquePathsIII(grid1) << endl;
    cout << sol.uniquePathsIII(grid2) << endl;

    return 0;
}